#include <vector>
#include <unordered_map>
using namespace std;


// version 1
class Solution {
private:
//最多遍历3次，常数级别
    bool IsExistInFruit(const vector<pair<int, int>>& basket, int num){
        for(auto& v : basket){
            if(v.first == num) return true;
        }
        return false;
    }
public:
    int totalFruit(vector<int>& fruits) {
        //pair中，前者是树的种类，后者是个数
        vector<pair<int, int>> basket;

        //必须等到有一个篮子空了，才能停止出窗口
        int tree_num = basket.size(), ret = 0;
        for(int left = 0, right = 0; right < fruits.size(); ++right){
            //1.先入窗口
            if(tree_num == 0 || !IsExistInFruit(basket, fruits[right])) {
                basket.push_back({fruits[right], 1});
                tree_num = basket.size();
            }
            else{
                if(basket[0].first == fruits[right]) (basket[0].second)++;
                else (basket[1].second)++;
            }

            //不满足窗口 -> 调整
            while(tree_num > 2){
                int tmp = fruits[left++];
                if(tmp == basket[0].first) (basket[0].second)--;
                else (basket[1].second)--;

                if(basket[0].second == 0 || basket[1].second == 0){ 
                    if(basket[0].second == 0) basket.erase(basket.begin());
                    else basket.erase(basket.begin() + 1);
                }
                tree_num = basket.size();
            }
            //更新结果
            ret = std::max(ret, right - left + 1);
        }
        return ret;
    }
};


//version 2 使用哈希表
class Solution {
private:
public:
    int totalFruit(vector<int>& fruits) {
        //前者是树的种类，后者是个数
        unordered_map<int, int> basket;

        //经过分析，必须要让第一个篮子空，才有意义，否则没有用
        int tree_num = basket.size(), ret = 0;
        for(int left = 0, right = 0; right < fruits.size(); ++right){
            //1.先入窗口
            basket[fruits[right]]++;
            tree_num = basket.size();

            //不满足窗口 -> 调整
            while(tree_num > 2){
                int tmp = fruits[left++];
                basket[tmp]--;
                if(basket[tmp] == 0){
                    basket.erase(tmp);
                    tree_num = basket.size();
                }
            }
            ret = std::max(ret, right - left + 1);
        }
        return ret;
    }
};
//但是时间复杂度不如上面一个